use anyhow::{Error, Result};
use std::cell::RefCell;
use std::fmt::Debug;
use std::sync::Arc;
use tokio::sync::RwLock;
use uuid::Uuid;

pub mod bit;
mod cache;
pub mod cmd;
pub mod net;
pub mod timeout_map;
pub mod validator;

trait LinkList<T> {
    type Result;
    fn len(&self) -> usize;
    fn is_empty(&self) -> bool;
    fn head(&self) -> Option<Self::Result>;
    fn tail(&self) -> Option<Self::Result>;
    fn push_head(&mut self, data: T) -> Result<Self::Result>;
    fn push_tail(&mut self, data: T) -> Result<Self::Result>;
    fn pop_head(&mut self) -> Option<Self::Result>;
    fn pop_tail(&mut self) -> Option<Self::Result>;
    fn index(&self, index: usize) -> Option<Self::Result>;
    fn remove(&mut self, node: &Self::Result) -> Result<()>;
    fn remove_by_index(&mut self, index: usize) -> Result<Self::Result>;
    fn insert_after(&mut self, node: &Self::Result, data: T) -> Result<Self::Result>;
    fn insert_before(&mut self, node: &Self::Result, data: T) -> Result<Self::Result>;
}

trait LinkListExt<T>
where
    T: Eq + PartialEq,
{
    type Result;
    fn swap(&mut self, a: &Self::Result, b: &Self::Result) -> Result<()>;
    fn move_head(&mut self, node: &Self::Result) -> Result<()>;
    fn move_tail(&mut self, node: &Self::Result) -> Result<()>;
    fn index_of(&self, node: &Self::Result, io: IterationOrder) -> Result<usize>;
}

#[derive(Debug, Hash, PartialEq, Eq, Clone, Copy)]
pub enum IterationOrder {
    FromHead,
    FromTail,
    BothDirection,
}

const ERR_NOT_LINKED_LIST: &str = "输入的节点不属于该链表";

type Node<T> = Arc<RefCell<LinkNode<T>>>;

/// 单线程链表
#[derive(Eq, PartialEq, Debug)]
pub struct LinkedList<T> {
    head: Option<Node<T>>,
    tail: Option<Node<T>>,
    len: usize,
    uuid: Uuid, // uuid，用于标识链表
}

/// 单线程链表节点
#[derive(Eq, PartialEq, Debug)]
pub struct LinkNode<T> {
    pub data: T,
    next: Option<Node<T>>,
    prev: Option<Node<T>>,
    link: Uuid, // 用于标识所属链表
}

impl<T> LinkNode<T> {
    pub fn new(data: T) -> Node<T> {
        Arc::new(RefCell::new(LinkNode {
            data,
            next: None,
            prev: None,
            link: Uuid::nil(),
        }))
    }

    pub fn data_ref(&self) -> &T {
        &self.data
    }
    pub fn next(&self) -> Option<&Node<T>> {
        self.next.as_ref()
    }
    pub fn prev(&self) -> Option<&Node<T>> {
        self.prev.as_ref()
    }

    /// 试图从Node<T>中获取值T，如果失败，则返回原值
    pub fn try_into(n: Node<T>) -> Result<T, Node<T>> {
        if !n.borrow().next.is_none()
            || !n.borrow().prev.is_none()
            || n.borrow().link != Uuid::nil()
        {
            return Err(n);
        }
        if Arc::strong_count(&n) == 1 {
            let a = Arc::into_inner(n).unwrap();
            return Ok(RefCell::into_inner(a).data);
        }
        Err(n)
    }
}

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        LinkedList {
            head: None,
            tail: None,
            len: 0,
            uuid: Uuid::now_v7(),
        }
    }
}

impl<T> LinkList<T> for LinkedList<T> {
    type Result = Node<T>;

    fn len(&self) -> usize {
        self.len
    }

    fn is_empty(&self) -> bool {
        self.len == 0
    }

    fn head(&self) -> Option<Node<T>> {
        self.head.clone()
    }

    fn tail(&self) -> Option<Node<T>> {
        self.tail.clone()
    }

    /// 向头部插入一个节点
    fn push_head(&mut self, t: T) -> Result<Node<T>, Error> {
        let node = LinkNode::<T>::new(t);
        node.borrow_mut().link = self.uuid.clone();
        match self.head.take() {
            None => {
                self.head = Some(node.clone());
                self.tail = Some(node.clone());
            }
            Some(old_head) => {
                old_head.borrow_mut().prev = Some(node.clone());
                self.head = Some(node.clone());
                node.borrow_mut().next = Some(old_head.clone());
            }
        }
        self.len += 1;
        Ok(node)
    }

    /// 向尾部插入一个节点
    fn push_tail(&mut self, t: T) -> Result<Node<T>> {
        let node = LinkNode::<T>::new(t);
        node.borrow_mut().link = self.uuid.clone();
        match self.tail.take() {
            None => {
                self.head = Some(node.clone());
                self.tail = Some(node.clone());
            }
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(node.clone());
                self.tail = Some(node.clone());
                node.borrow_mut().prev = Some(old_tail.clone());
            }
        }
        self.len += 1;
        Ok(node)
    }

    fn pop_head(&mut self) -> Option<Node<T>> {
        if self.head.is_none() {
            return None;
        }
        let result = self.head.take().unwrap();
        self.head = result.borrow().next.clone();
        if self.head.is_some() {
            self.head.as_ref().unwrap().borrow_mut().prev = None;
        } else {
            self.tail = None;
        }
        result.borrow_mut().prev = None;
        result.borrow_mut().next = None;
        result.borrow_mut().link = Uuid::nil();
        self.len -= 1;
        Some(result)
    }

    fn pop_tail(&mut self) -> Option<Node<T>> {
        if self.tail.is_none() {
            return None;
        }
        let result = self.tail.take().unwrap();
        self.tail = result.borrow().prev.clone();

        if self.tail.is_some() {
            self.tail.as_ref().unwrap().borrow_mut().next = None;
        } else {
            self.head = None;
        }

        result.borrow_mut().prev = None;
        result.borrow_mut().next = None;
        result.borrow_mut().link = Uuid::nil();
        self.len -= 1;
        Some(result)
    }

    /// 给出节点索引，返回节点，索引是从0开始的
    fn index(&self, index: usize) -> Option<Node<T>> {
        if index >= self.len {
            return None;
        }
        let from_head = (self.len + 1) / 2 > index;
        if from_head {
            // 从头部迭代比较好
            let mut node = self.head.clone().unwrap();
            if index == 0 {
                return Some(node);
            }
            for _i in 0..index {
                let v = node.borrow().next.clone().unwrap();
                node = v;
            }
            Some(node)
        } else {
            // 从尾部迭代比较好
            let mut node = self.tail.clone().unwrap();
            if index == self.len - 1 {
                return Some(node);
            }
            for _i in 0..(self.len - 1 - index) {
                let v = node.borrow().prev.clone().unwrap();
                node = v;
            }
            Some(node)
        }
    }

    fn remove(&mut self, node: &Node<T>) -> Result<()> {
        if self.uuid != node.borrow().link {
            return Err(Error::msg(ERR_NOT_LINKED_LIST));
        }
        match (node.borrow().next.is_some(), node.borrow().prev.is_some()) {
            (true, true) => {
                let next = node.borrow().next.clone().unwrap();
                let prev = node.borrow().prev.clone().unwrap();
                prev.borrow_mut().next = Some(next.clone());
                next.borrow_mut().prev = Some(prev.clone());
            }
            (true, false) => {
                let next = node.borrow().next.clone().unwrap();
                self.head = Some(next.clone());
                next.borrow_mut().prev = None;
            }
            (false, true) => {
                let prev = node.borrow().prev.clone().unwrap();
                self.tail = Some(prev.clone());
                prev.borrow_mut().next = None;
            }
            (false, false) => {
                self.head = None;
                self.tail = None;
            }
        }
        self.len -= 1;
        node.borrow_mut().next = None;
        node.borrow_mut().prev = None;
        node.borrow_mut().link = Uuid::nil();
        Ok(())
    }

    /// 删除指定索引的节点，并返回该节点
    fn remove_by_index(&mut self, i: usize) -> Result<Node<T>> {
        let node = self.index(i);
        if node.is_none() {
            return Err(Error::msg("index out of bounds"));
        }
        let n = node.unwrap();
        self.remove(&n)?;
        Ok(n)
    }

    fn insert_after(&mut self, i: &Node<T>, t: T) -> Result<Node<T>> {
        if self.uuid != i.borrow().link {
            return Err(Error::msg(ERR_NOT_LINKED_LIST));
        }
        let node = LinkNode::new(t);
        node.borrow_mut().link = self.uuid.clone();
        self.len += 1;
        let next = i.borrow().next.clone();
        if next.is_some() {
            next.as_ref().unwrap().borrow_mut().prev = Some(node.clone());
            node.borrow_mut().next = next;
        } else {
            // i是最后一个节点
            self.tail = Some(node.clone());
        }
        i.borrow_mut().next = Some(node.clone());
        node.borrow_mut().prev = Some(i.clone());
        Ok(node)
    }

    fn insert_before(&mut self, i: &Node<T>, t: T) -> Result<Node<T>> {
        if self.uuid != i.borrow().link {
            return Err(Error::msg(ERR_NOT_LINKED_LIST));
        }
        let node = LinkNode::new(t);
        node.borrow_mut().link = self.uuid.clone();
        self.len += 1;
        let prev = i.borrow().prev.clone();
        if prev.is_some() {
            prev.as_ref().unwrap().borrow_mut().next = Some(node.clone());
            node.borrow_mut().prev = prev;
        } else {
            // i是第一个节点
            self.head = Some(node.clone());
        }
        i.borrow_mut().prev = Some(node.clone());
        node.borrow_mut().next = Some(i.clone());
        Ok(node)
    }
}

impl<T> LinkListExt<T> for LinkedList<T>
where
    T: PartialEq + Eq,
{
    type Result = Node<T>;

    fn swap(&mut self, i: &Node<T>, j: &Node<T>) -> Result<()> {
        if self.uuid != i.borrow().link || self.uuid != j.borrow().link {
            return Err(Error::msg(ERR_NOT_LINKED_LIST));
        }
        if Arc::ptr_eq(i, j) {
            return Err(Error::msg("参数i和j是同一个Arc的副本"));
        }

        // 判断i和j是否相邻
        if i.borrow().next == Some(j.clone()) {
            // 相邻，i的下一个是j
            let j_next = j.borrow_mut().next.take();
            let i_prev = i.borrow_mut().prev.take();
            if let Some(x) = j_next {
                x.borrow_mut().prev = Some(i.clone());
                i.borrow_mut().next = Some(x.clone());
            } else {
                self.tail = Some(i.clone());
            }
            if let Some(x) = i_prev {
                // i有上一个节点，i不是第一个节点
                x.borrow_mut().next = Some(j.clone());
                j.borrow_mut().prev = Some(x.clone());
            } else {
                // i没有上一个节点，i是第一个节点
                self.head = Some(j.clone());
            }
            j.borrow_mut().next = Some(i.clone());
            i.borrow_mut().prev = Some(j.clone());
            return Ok(());
        }
        if j.borrow().prev == Some(i.clone()) {
            // 相邻，j的下一个是i
            let i_next = i.borrow_mut().next.take();
            let j_prev = j.borrow_mut().prev.take();
            if let Some(x) = i_next {
                x.borrow_mut().prev = Some(j.clone());
                j.borrow_mut().next = Some(x.clone());
            } else {
                // i没有下一个节点，i是最后一个节点
                self.tail = Some(j.clone());
            }
            if let Some(x) = j_prev {
                // j有上一个节点，j不是第一个节点
                x.borrow_mut().next = Some(i.clone());
                i.borrow_mut().prev = Some(x.clone());
            } else {
                // 节点j没有上一个节点，j是第一个节点
                self.head = Some(i.clone());
            }
            j.borrow_mut().prev = Some(i.clone());
            i.borrow_mut().next = Some(j.clone());
            return Ok(());
        }

        // 不相邻
        let i_next = i.borrow_mut().next.take();
        let j_next = j.borrow_mut().next.take();
        let i_prev = i.borrow_mut().prev.take();
        let j_prev = j.borrow_mut().prev.take();
        if let Some(x) = j_prev {
            // j有上一个节点，j不是第一个节点
            x.borrow_mut().next = Some(i.clone());
            i.borrow_mut().prev = Some(x.clone());
        } else {
            // 节点j没有上一个节点，j是第一个节点
            self.head = Some(i.clone());
        }
        if let Some(x) = j_next {
            x.borrow_mut().prev = Some(i.clone());
            i.borrow_mut().next = Some(x.clone());
        } else {
            // 节点j没有下一个节点，j是最后一个节点
            self.tail = Some(i.clone());
        }
        if let Some(x) = i_prev {
            // i有上一个节点，i不是第一个节点
            x.borrow_mut().next = Some(j.clone());
            j.borrow_mut().prev = Some(x.clone());
        } else {
            // i没有上一个节点，i是第一个节点
            self.head = Some(j.clone());
        }
        if let Some(x) = i_next {
            x.borrow_mut().prev = Some(j.clone());
            j.borrow_mut().next = Some(x.clone());
        } else {
            // i没有下一个节点，i是最后一个节点
            self.tail = Some(j.clone());
        }
        Ok(())
    }

    /// 将i移动到链表头部
    fn move_head(&mut self, i: &Node<T>) -> Result<()> {
        self.swap(i, &mut self.head().unwrap())
    }

    /// 将i移动到链表尾部
    fn move_tail(&mut self, i: &Node<T>) -> Result<()> {
        self.swap(i, &mut self.tail().unwrap())
    }

    /// 给出节点的序号
    fn index_of(&self, i: &Node<T>, io: IterationOrder) -> Result<usize> {
        if self.uuid != i.borrow().link || self.is_empty() {
            return Err(Error::msg(ERR_NOT_LINKED_LIST));
        }
        match io {
            IterationOrder::FromHead => {
                let mut result = 0;
                for node in self {
                    if Arc::ptr_eq(i, &node) {
                        return Ok(result);
                    }
                    result += 1;
                }
                Err(Error::msg(ERR_NOT_LINKED_LIST))
            }
            IterationOrder::FromTail => {
                let mut result = self.len();
                let mut node = self.tail.clone().unwrap();
                while result > 0 {
                    if Arc::ptr_eq(i, &node) {
                        return Ok(result - 1);
                    }
                    result -= 1;
                    if node.borrow().prev.is_some() {
                        let prev = node.borrow().prev.clone().unwrap();
                        node = prev;
                    } else {
                        break;
                    }
                }
                Err(Error::msg(ERR_NOT_LINKED_LIST))
            }
            IterationOrder::BothDirection => {
                let mut rh = 0;
                let (mut rt, len) = (self.len(), self.len());
                let mut nh = self.head.clone().unwrap();
                let mut nt = self.tail.clone().unwrap();
                while rt > 0 && rh < len && rh <= rt {
                    if Arc::ptr_eq(i, &nh) {
                        return Ok(rh);
                    } else {
                        rh += 1;
                        let next = nh.borrow().next.clone().unwrap();
                        nh = next;
                    }
                    if Arc::ptr_eq(i, &nt) {
                        return Ok(rt - 1);
                    } else {
                        rt -= 1;
                        let prev = nt.borrow().prev.clone().unwrap();
                        nt = prev;
                    }
                }
                Err(Error::msg(ERR_NOT_LINKED_LIST))
            }
        }
    }
}

impl<'a, T> IntoIterator for &'a LinkedList<T> {
    type Item = Node<T>;
    type IntoIter = _IterLinkedList<'a, T>;
    fn into_iter(self) -> Self::IntoIter {
        Self::IntoIter::new(self)
    }
}

pub struct _IterLinkedList<'a, T> {
    list: &'a LinkedList<T>,
    node: Option<Node<T>>,
}

impl<'a, T> Iterator for _IterLinkedList<'a, T> {
    type Item = Node<T>;

    fn next(&mut self) -> Option<Self::Item> {
        let result = self.node.clone();
        let node = self.node.take();
        if let Some(n) = node {
            self.node = n.borrow().next.clone();
        }
        match result {
            None => None,
            Some(r) => Some(r.clone()),
        }
    }
}

impl<'a, T> _IterLinkedList<'a, T> {
    pub fn new(l: &'a LinkedList<T>) -> Self {
        let mut r = _IterLinkedList {
            list: l,
            node: None,
        };
        if !r.list.is_empty() {
            r.node = r.list.head.clone();
        }
        r
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        if self.is_empty() {
            return;
        }
        while self.head.is_some() {
            if let Some(n) = self.pop_head() {
                drop(n);
            }
        }
    }
}

#[test]
fn test_linked_list1() {
    let mut list = LinkedList::<i32>::new();
    let n1 = list.push_tail(1).unwrap();
    let n2 = list.push_tail(2).unwrap();
    let n3 = list.push_tail(3).unwrap();
    let n4 = list.push_tail(4).unwrap();
    let n5 = list.push_tail(5).unwrap();
    let n6 = list.push_tail(6).unwrap();
    list.push_tail(7).unwrap();
    let n = list.pop_tail().unwrap();

    println!("len: {}", list.len());

    assert_eq!(list.index_of(&n1, IterationOrder::FromHead).unwrap(), 0);
    assert_eq!(list.index_of(&n2, IterationOrder::FromHead).unwrap(), 1);
    assert_eq!(list.index_of(&n3, IterationOrder::FromHead).unwrap(), 2);
    assert_eq!(list.index_of(&n4, IterationOrder::FromHead).unwrap(), 3);
    assert_eq!(list.index_of(&n5, IterationOrder::FromHead).unwrap(), 4);

    assert_eq!(list.index_of(&n1, IterationOrder::FromTail).unwrap(), 0);
    assert_eq!(list.index_of(&n2, IterationOrder::FromTail).unwrap(), 1);
    assert_eq!(list.index_of(&n3, IterationOrder::FromTail).unwrap(), 2);
    assert_eq!(list.index_of(&n4, IterationOrder::FromTail).unwrap(), 3);
    assert_eq!(list.index_of(&n5, IterationOrder::FromTail).unwrap(), 4);

    assert_eq!(
        list.index_of(&n1, IterationOrder::BothDirection).unwrap(),
        0
    );
    assert_eq!(
        list.index_of(&n2, IterationOrder::BothDirection).unwrap(),
        1
    );
    assert_eq!(
        list.index_of(&n3, IterationOrder::BothDirection).unwrap(),
        2
    );
    assert_eq!(
        list.index_of(&n4, IterationOrder::BothDirection).unwrap(),
        3
    );
    assert_eq!(
        list.index_of(&n5, IterationOrder::BothDirection).unwrap(),
        4
    );
    assert_eq!(
        list.index_of(&n6, IterationOrder::BothDirection).unwrap(),
        5
    );

    let _ = list.index_of(&n, IterationOrder::BothDirection);
}

#[test]
fn test_linked_list2() {
    let mut list = LinkedList::<i32>::new();
    list.push_tail(1).unwrap();
    list.push_tail(2).unwrap();
    list.push_tail(3).unwrap();
    list.push_tail(4).unwrap();
    let mut index = 1;
    while !list.is_empty() {
        assert_eq!(LinkNode::try_into(list.pop_head().unwrap()).unwrap(), index);
        index += 1;
    }

    let mut list = LinkedList::<i32>::new();
    list.push_head(1).unwrap();
    list.push_head(2).unwrap();
    list.push_head(3).unwrap();
    list.push_head(4).unwrap();
    let mut index = 1;
    while !list.is_empty() {
        assert_eq!(LinkNode::try_into(list.pop_tail().unwrap()).unwrap(), index);
        index += 1;
    }

    let mut list = LinkedList::<i32>::new();
    list.push_head(1).unwrap();
    list.push_head(2).unwrap();
    list.push_head(3).unwrap();
    list.push_head(4).unwrap();
    let mut index = 4;
    while !list.is_empty() {
        assert_eq!(
            LinkNode::try_into(list.remove_by_index(0).unwrap()).unwrap(),
            index
        );
        index -= 1;
    }

    let mut list = LinkedList::<i32>::new();
    let mut n = list.push_head(1).unwrap();
    list.insert_before(&n, 0).unwrap();
    list.insert_after(&n, 2).unwrap();
    println!("n: {}", n.borrow().data);
    while !list.is_empty() {
        print!("{} ", list.pop_head().unwrap().borrow().data)
    }
    print!("\n");

    list.push_tail(1).unwrap();
    n = list.push_head(2).unwrap();
    list.push_head(3).unwrap();
    list.remove(&n).unwrap();
    while !list.is_empty() {
        print!("{} ", list.pop_head().unwrap().borrow().data)
    }
    print!("\n");
    list.push_tail(1).unwrap();
    list.push_tail(2).unwrap();
    list.push_tail(3).unwrap();
    list.push_tail(4).unwrap();
    list.pop_head().unwrap();
    list.pop_tail().unwrap();
    while !list.is_empty() {
        print!("{} ", list.pop_head().unwrap().borrow().data)
    }
}

// 以下是对异步链表的实现
// 链表的并发安全性由两部分组成：
// 1. 链表节点顺序的读写，仅当插入、删除、交换链表节点才算写，遍历、读取链表的某个节点为读操作
// 2. 链表节点数据的读写
// 在本场景中，认为上述两者是互不干扰的

/// 约定：仅当要修改RwNode的data字段时，才使用RwNode的可变引用
type RwNode<T> = Arc<RwLock<RwLinkNode<T>>>;

#[derive(Debug)]
pub struct RwLinkNode<T> {
    pub data: T,
    next: Option<RwNode<T>>,
    prev: Option<RwNode<T>>,
    link: Uuid, // 用于标识所属链表
}

impl<T> RwLinkNode<T> {
    pub fn new(data: T) -> RwNode<T> {
        Arc::new(RwLock::new(RwLinkNode {
            data,
            next: None,
            prev: None,
            link: Uuid::nil(),
        }))
    }

    pub fn try_into_inner(node: RwNode<T>) -> Result<T, RwNode<T>> {
        let mut can_into_inner = false;
        if Arc::strong_count(&node) == 1 {
            can_into_inner = true;
        }
        if can_into_inner {
            let s = Arc::into_inner(node).unwrap();
            return Ok(RwLock::into_inner(s).data);
        }
        Err(node)
    }
}

impl<T> PartialEq for RwLinkNode<T>
where
    T: PartialEq + Eq,
{
    /// 节点所属的链表相同且包含的数据相同时，如果两者的上一个节点和下一个节点都相同，就是同一个节点。<br/>
    /// 当两个节点都是孤儿节点时，内部包含的数据一致，就认为是相同的节点。
    fn eq(&self, other: &RwLinkNode<T>) -> bool {
        if self.data == other.data && self.link == other.link {
            if self.next.is_some() || other.next.is_some() {
                if self.next.is_some() && other.next.is_some() {
                    if !Arc::ptr_eq(&self.next.as_ref().unwrap(), &other.next.as_ref().unwrap()) {
                        return false;
                    }
                } else {
                    return false;
                }
            }
            if self.prev.is_some() || other.prev.is_some() {
                if self.prev.is_some() && other.prev.is_some() {
                    if !Arc::ptr_eq(&self.prev.as_ref().unwrap(), &other.prev.as_ref().unwrap()) {
                        return false;
                    }
                } else {
                    return false;
                }
            }
            true
        } else {
            false
        }
    }
}

pub type ConcurrentLinkedList<T> = Arc<RwLock<RwLinkedList<T>>>;

#[derive(Debug)]
pub struct RwLinkedList<T> {
    head: Option<RwNode<T>>,
    tail: Option<RwNode<T>>,
    len: usize,
    uuid: Uuid,
}

impl<T> RwLinkedList<T> {
    pub fn new() -> Self {
        RwLinkedList {
            head: None,
            tail: None,
            len: 0,
            uuid: Uuid::now_v7(),
        }
    }

    pub fn new_concurrent() -> ConcurrentLinkedList<T> {
        Arc::new(RwLock::new(Self::new()))
    }

    fn len(&self) -> usize {
        self.len
    }

    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    fn head(&self) -> Option<RwNode<T>> {
        self.head.clone()
    }

    fn tail(&self) -> Option<RwNode<T>> {
        self.tail.clone()
    }

    /// 获取node的下一个节点<br/>
    /// 之所以获取下一个节点需要链表，是为了让链表上读锁，防止获取下一个节点时修改节点数和顺序
    async fn next(&self, node: &RwNode<T>) -> Result<Option<RwNode<T>>> {
        if self.uuid != node.read().await.link {
            return Err(Error::msg(ERR_NOT_LINKED_LIST));
        }
        Ok(node.read().await.next.clone())
    }

    async fn prev(&self, node: &RwNode<T>) -> Result<Option<RwNode<T>>> {
        if self.uuid != node.read().await.link {
            return Err(Error::msg(ERR_NOT_LINKED_LIST));
        }
        Ok(node.read().await.prev.clone())
    }

    async fn push_head(&mut self, data: T) -> Result<RwNode<T>> {
        let node = RwLinkNode::new(data);
        node.write().await.link = self.uuid;
        match self.head.take() {
            None => {
                self.tail = Some(node.clone());
                self.head = Some(node.clone());
            }
            Some(old_head) => {
                node.write().await.next = Some(old_head.clone());
                old_head.write().await.prev = Some(node.clone());
                self.head = Some(node.clone());
            }
        }
        self.len += 1;
        Ok(node)
    }

    async fn push_tail(&mut self, data: T) -> Result<RwNode<T>> {
        let node = RwLinkNode::new(data);
        node.write().await.link = self.uuid;
        match self.tail.take() {
            None => {
                self.head = Some(node.clone());
                self.tail = Some(node.clone());
            }
            Some(old_tail) => {
                node.write().await.prev = Some(old_tail.clone());
                old_tail.write().await.next = Some(node.clone());
                self.tail = Some(node.clone());
            }
        }
        self.len += 1;
        Ok(node)
    }

    async fn pop_head(&mut self) -> Option<RwNode<T>> {
        if self.head.is_none() {
            return None;
        }
        let head = self.head.take().unwrap();
        match head.read().await.next.clone() {
            None => {
                // 只有一个节点了
                self.head = None;
                self.tail = None;
            }
            Some(new_head) => {
                // 还有多个节点
                self.head = Some(new_head.clone());
                new_head.write().await.prev = None;
            }
        }
        let mut s = head.write().await;
        s.next = None;
        s.prev = None;
        s.link = Uuid::nil();
        self.len -= 1;
        drop(s);
        Some(head)
    }

    async fn pop_tail(&mut self) -> Option<RwNode<T>> {
        if self.tail.is_none() {
            return None;
        }
        let tail = self.tail.take().unwrap();
        match tail.read().await.prev.clone() {
            None => {
                // 只有一个节点了
                self.head = None;
                self.tail = None;
            }
            Some(new_tail) => {
                // 还有多个节点
                self.head = Some(new_tail.clone());
                new_tail.write().await.prev = None;
            }
        }
        let mut s = tail.write().await;
        s.next = None;
        s.prev = None;
        s.link = Uuid::nil();
        self.len -= 1;
        drop(s);
        Some(tail)
    }

    async fn index(&self, index: usize) -> Option<RwNode<T>> {
        if index >= self.len {
            return None;
        }
        let from_head = (self.len + 1) / 2 > index;
        if from_head {
            // 从头部迭代比较好
            let mut node = self.head.clone().unwrap();
            if index == 0 {
                return Some(node);
            }
            for _i in 0..index {
                let v = node.read().await.next.clone().unwrap();
                node = v;
            }
            Some(node)
        } else {
            // 从尾部迭代比较好
            let mut node = self.tail.clone().unwrap();
            if index == self.len - 1 {
                return Some(node);
            }
            for _i in 0..index {
                let v = node.read().await.prev.clone().unwrap();
                node = v;
            }
            Some(node)
        }
    }

    async fn remove(&mut self, node: &RwNode<T>) -> Result<()> {
        if self.uuid != node.read().await.link {
            return Err(Error::msg(ERR_NOT_LINKED_LIST));
        }
        match (
            node.read().await.next.is_some(),
            node.read().await.prev.is_some(),
        ) {
            (true, true) => {
                let next = node.read().await.next.clone().unwrap();
                let prev = node.read().await.prev.clone().unwrap();
                prev.write().await.next = Some(next.clone());
                next.write().await.prev = Some(prev.clone());
            }
            (true, false) => {
                let next = node.read().await.next.clone().unwrap();
                self.head = Some(next.clone());
                next.write().await.prev = None;
            }
            (false, true) => {
                let prev = node.read().await.prev.clone().unwrap();
                self.tail = Some(prev.clone());
                prev.write().await.next = None;
            }
            (false, false) => {
                self.head = None;
                self.tail = None;
            }
        }
        self.len -= 1;
        let mut mut_node = node.write().await;
        mut_node.link = Uuid::nil();
        mut_node.next = None;
        mut_node.prev = None;
        drop(mut_node);
        Ok(())
    }

    async fn remove_by_index(&mut self, index: usize) -> Result<RwNode<T>> {
        let node = self.index(index).await;
        if node.is_none() {
            return Err(Error::msg("index out of bounds"));
        }
        let n = node.unwrap();
        self.remove(&n).await?;
        Ok(n)
    }

    async fn insert_after(&mut self, i: &RwNode<T>, data: T) -> Result<RwNode<T>> {
        let mut i_ref = i.write().await;
        if self.uuid != i_ref.link {
            return Err(Error::msg(ERR_NOT_LINKED_LIST));
        }
        let node = RwLinkNode::new(data);
        let mut node_ref = node.write().await;
        node_ref.link = self.uuid;
        self.len += 1;
        let next = i_ref.next.clone();
        if next.is_some() {
            next.as_ref().unwrap().write().await.prev = Some(node.clone());
            node_ref.next = next;
        } else {
            self.tail = Some(node.clone());
        }
        i_ref.next = Some(node.clone());
        node_ref.prev = Some(i.clone());
        drop(node_ref);
        Ok(node)
    }

    async fn insert_before(&mut self, i: &RwNode<T>, data: T) -> Result<RwNode<T>> {
        let mut i_ref = i.write().await;
        if self.uuid != i_ref.link {
            return Err(Error::msg(ERR_NOT_LINKED_LIST));
        }
        let node = RwLinkNode::new(data);
        let mut node_ref = node.write().await;
        node_ref.link = self.uuid;
        self.len += 1;
        let prev = i_ref.prev.clone();
        if prev.is_some() {
            prev.as_ref().unwrap().write().await.next = Some(node.clone());
            node_ref.prev = prev;
        } else {
            self.head = Some(node.clone());
        }
        i_ref.prev = Some(node.clone());
        node_ref.next = Some(i.clone());
        drop(node_ref);
        Ok(node)
    }
}

impl<T> RwLinkedList<T>
where
    T: PartialEq + Eq,
{
    async fn swap(&mut self, a: &RwNode<T>, b: &RwNode<T>) -> Result<()> {
        let (mut a_ref, mut b_ref) = (a.write().await, b.write().await);
        if self.uuid != a_ref.link || self.uuid != b_ref.link {
            return Err(Error::msg(ERR_NOT_LINKED_LIST));
        }
        if Arc::ptr_eq(&a, &b) {
            return Err(Error::msg("参数a和b时同一个Arc的副本"));
        }
        if a_ref.next.is_some() && Arc::ptr_eq(a_ref.next.as_ref().unwrap(), b) {
            // a和b相邻，a的下一个就是b
            let a_prev = a_ref.prev.take();
            let b_next = b_ref.next.take();
            if let Some(x) = a_prev {
                // a有上一个节点，a不是第一个节点
                x.write().await.next = Some(b.clone());
                b_ref.prev = Some(x.clone());
            } else {
                // a是第一个节点
                self.head = Some(b.clone());
            }
            if let Some(x) = b_next {
                // b有下一个节点，b不是最后一个节点
                a_ref.next = Some(x.clone());
                x.write().await.prev = Some(a.clone());
            } else {
                // b是最后一个节点
                self.tail = Some(a.clone());
            }
            a_ref.prev = Some(b.clone());
            b_ref.next = Some(a.clone());
            return Ok(());
        }
        if b_ref.next.is_some() && Arc::ptr_eq(b_ref.next.as_ref().unwrap(), a) {
            // a和b相邻，b的下一个就是a
            let b_prev = b_ref.prev.take();
            let a_next = a_ref.next.take();
            if let Some(x) = b_prev {
                // b有上一个节点，b不是第一个节点
                x.write().await.next = Some(a.clone());
                a_ref.prev = Some(x);
            } else {
                // b是第一个节点
                self.head = Some(a.clone());
            }
            if let Some(x) = a_next {
                // a有下一个节点，a不是最后一个节点
                x.write().await.prev = Some(b.clone());
                b_ref.next = Some(x);
            } else {
                // a没有下一个节点，a是最后一个节点
                self.tail = Some(b.clone());
            }
            a_ref.next = Some(b.clone());
            b_ref.prev = Some(a.clone());
            return Ok(());
        }
        // a和b不相邻
        let a_next = a_ref.next.take();
        let a_prev = a_ref.prev.take();
        let b_next = b_ref.next.take();
        let b_prev = b_ref.prev.take();
        if let Some(x) = a_next {
            // a有下一个节点，a不是最后一个节点
            x.write().await.prev = Some(b.clone());
            b_ref.next = Some(x);
        } else {
            // a没有下一个节点，a是最后一个节点
            self.tail = Some(b.clone());
        }
        if let Some(x) = a_prev {
            // a有上一个节点，a不是第一个节点
            x.write().await.next = Some(b.clone());
            b_ref.prev = Some(x);
        } else {
            // a是第一个节点
            self.head = Some(b.clone());
        }
        if let Some(x) = b_next {
            // b有下一个节点，b不是最后一个节点
            x.write().await.prev = Some(a.clone());
            a_ref.next = Some(x);
        } else {
            // b是最后一个节点
            self.tail = Some(a.clone());
        }
        if let Some(x) = b_prev {
            // b有上一个节点，b不是第一个节点
            x.write().await.next = Some(a.clone());
            a_ref.prev = Some(x);
        } else {
            // b是第一个节点
            self.head = Some(a.clone());
        }
        Ok(())
    }

    async fn move_head(&mut self, a: &RwNode<T>) -> Result<()> {
        self.swap(&a, &self.head().unwrap()).await
    }

    async fn move_tail(&mut self, a: &mut RwNode<T>) -> Result<()> {
        self.swap(&a, &self.tail().unwrap()).await
    }

    async fn index_of(&self, a: &RwNode<T>, io: IterationOrder) -> Result<usize> {
        if self.uuid != a.read().await.link || self.is_empty() {
            return Err(Error::msg(ERR_NOT_LINKED_LIST));
        }
        match io {
            IterationOrder::FromHead => {
                let mut result = 0;
                let mut index = self.head();
                while index.is_some() {
                    if Arc::ptr_eq(&index.as_ref().unwrap(), a) {
                        return Ok(result);
                    }
                    index = self.next(index.as_ref().unwrap()).await?;
                    result += 1;
                }
                Err(Error::msg(ERR_NOT_LINKED_LIST))
            }
            IterationOrder::FromTail => {
                let mut result = self.len() - 1;
                let mut index = self.tail();
                while index.is_some() {
                    if Arc::ptr_eq(&index.as_ref().unwrap(), a) {
                        return Ok(result);
                    }
                    index = self.prev(index.as_ref().unwrap()).await?;
                    result -= 1;
                }
                Err(Error::msg(ERR_NOT_LINKED_LIST))
            }
            IterationOrder::BothDirection => {
                let mut rh = 0;
                let (mut rt, len) = (self.len(), self.len());
                let mut nh = self.head();
                let mut nt = self.tail();
                while rt > 0 && rh < len && rh <= rt {
                    if nh.is_some() && Arc::ptr_eq(&nh.as_ref().unwrap(), a) {
                        return Ok(rh);
                    } else {
                        rh += 1;
                        nh = self.next(nh.as_ref().unwrap()).await?;
                    }
                    if nt.is_some() && Arc::ptr_eq(&nt.as_ref().unwrap(), a) {
                        return Ok(rt - 1);
                    } else {
                        rt -= 1;
                        nt = self.prev(nt.as_ref().unwrap()).await?;
                    }
                }
                Err(Error::msg(ERR_NOT_LINKED_LIST))
            }
        }
    }
}

// impl<T> Drop for RwLinkedList<T> {
//     fn drop(&mut self) {
//         todo!()
//     }
// }

#[test]
fn test_rw_eq() {
    let rw1 = RwLinkNode {
        data: 1,
        next: None,
        prev: None,
        link: Uuid::nil(),
    };
    let rw2 = RwLinkNode {
        data: 1,
        next: None,
        prev: None,
        link: Uuid::nil(),
    };

    if rw1 == rw2 {
        println!("eq")
    } else {
        println!("not eq")
    }

    let rw1 = RwLinkNode::new(1);
    let rw2 = RwLinkNode::new(1);
    let rw3 = rw1.clone();

    if Arc::ptr_eq(&rw1, &rw2) {
        println!("eq")
    } else {
        println!("not eq")
    }
    if Arc::ptr_eq(&rw1, &rw3) {
        println!("eq")
    } else {
        println!("not eq")
    }
}

#[tokio::test]
async fn test_rw_link() {
    let cl = RwLinkedList::<i32>::new_concurrent();

    let n1 = cl.write().await.push_tail(1).await.unwrap();
    let n2 = cl.write().await.push_tail(2).await.unwrap();
    let n3 = cl.write().await.push_tail(3).await.unwrap();
    let i = cl
        .read()
        .await
        .index_of(&n3, IterationOrder::FromHead)
        .await
        .unwrap();
    println!("{:?}", i);
    let i = cl
        .read()
        .await
        .index_of(&n1, IterationOrder::FromTail)
        .await
        .unwrap();
    println!("{:?}", i);
    let i = cl
        .read()
        .await
        .index_of(&n2, IterationOrder::FromHead)
        .await
        .unwrap();
    println!("{:?}", i);
    let h = cl.write().await.pop_head().await.unwrap();
    let r = match RwLinkNode::try_into_inner(h) {
        Ok(o) => {
            println!("into inner ok: {:?}", o);
            None
        }
        Err(e) => {
            println!("into inner err: {:?}", e);
            Some(e)
        }
    };
    if let Some(r) = r {
        drop(n1);
        println!("into inner ok: {}", RwLinkNode::try_into_inner(r).unwrap());
    }
}

async fn get_ref(rwn: &RwLock<RwLinkNode<i32>>) -> &RwLock<RwLinkNode<i32>> {
    let mut r = rwn.write().await;
    r.data += 1;
    drop(r);
    rwn
}

#[tokio::test]
async fn test_node() {
    let rwn = RwLock::new(RwLinkNode::<i32> {
        data: 1,
        next: None,
        prev: None,
        link: Uuid::nil(),
    });
    let r1 = &rwn;
    let r2 = &rwn;

    println!("{}", r1.read().await.data);
    println!("{}", r2.read().await.data);
    get_ref(&rwn).await;
    println!("{}", r1.read().await.data);
}
